#include "list.h"
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// 新建列表
List* ListNew(void) {
    List* list = malloc(sizeof(List));
    if (list == NULL) {
        fprintf(stderr, "ListNew: malloc failed\n");
        return NULL;
    }
    list->data = malloc(10 * sizeof(void*));
    if (list->data == NULL) {
        fprintf(stderr, "ListNew: malloc failed\n");
        free(list);
        return NULL;
    }
    list->capacity = 10;
    list->size = 0;
    return list;
}

// 在list末尾添加value
void ListAdd(List* list, void* value) {
    if (list == NULL) {
        fprintf(stderr, "ListAdd: list is NULL\n");
        return;
    }
    if (list->capacity < list->size + 1) {
        list->data = realloc(list->data, (list->capacity * 2) * sizeof(void*));
        if (list->data == NULL) {
            fprintf(stderr, "ListAdd: realloc failed\n");
            return;
        }
        list->capacity *= 2;
    }
    list->data[list->size++] = value;
}

// 从数组新建列表
List *ListFromArray(void **array, size_t size) {
  List *list = ListNew();
  if (list == NULL) {
    fprintf(stderr, "ListFromArray: ListNew failed\n");
    return NULL;
  }
  for (size_t i = 0; i < size; i++) {
    ListAdd(list, array[i]);
  }
  return list;
}

// 删除list中指定index的元素
void ListDelete(List* list, int index) {
    if (list == NULL) {
        fprintf(stderr, "ListDelete: list is NULL\n");
        return;
    }
    // 修复有符号和无符号整数比较问题
    if (index < 0) {
        // 处理负索引
        if (-index > (int)list->size) {
            fprintf(stderr, "ListDelete: index out of range\n");
            return;
        }
        index += list->size;
    } else {
        // 处理正索引
        if ((size_t)index >= list->size) {
            fprintf(stderr, "ListDelete: index out of range\n");
            return;
        }
    }
    for (size_t i = index; i < list->size - 1; i++) {
        list->data[i] = list->data[i + 1];
    }
    list->size--;
}

// 删除start到end的元素
void ListDeleteRange(List* list, int start, int end) {
    if (list == NULL) {
        fprintf(stderr, "ListDeleteRange: list is NULL\n");
        return;
    }
    
    // 修复有符号和无符号整数比较问题
    // 处理start索引
    if (start < 0) {
        if (-start > (int)list->size) {
            fprintf(stderr, "ListDeleteRange: index out of range\n");
            return;
        }
        start += list->size;
    } else {
        if ((size_t)start >= list->size) {
            fprintf(stderr, "ListDeleteRange: index out of range\n");
            return;
        }
    }
    
    // 处理end索引
    if (end < 0) {
        if (-end > (int)list->size) {
            fprintf(stderr, "ListDeleteRange: index out of range\n");
            return;
        }
        end += list->size;
    } else {
        if ((size_t)end > list->size) {
            fprintf(stderr, "ListDeleteRange: index out of range\n");
            return;
        }
    }
    
    for (size_t i = end; i < list->size; i++) {
        list->data[i - (end - start)] = list->data[i];
    }
    list->size -= end - start;
}

// 清空list
void ListClear(List* list) {
    if (list == NULL) {
        fprintf(stderr, "ListClear: list is NULL\n");
        return;
    }
    list->size = 0;
}

// 复制list到一个新列表
List* ListCopy(List* list) {
    if (list == NULL) {
        fprintf(stderr, "ListCopy: list is NULL\n");
        return NULL;
    }
    List* newList = malloc(sizeof(List));
    if (newList == NULL) {
        fprintf(stderr, "ListCopy: malloc failed\n");
        return NULL;
    }
    newList->data = malloc(list->capacity * sizeof(void*));
    if (newList->data == NULL) {
        fprintf(stderr, "ListCopy: malloc failed\n");
        free(newList);
        return NULL;
    }
    newList->capacity = list->capacity;
    newList->size = list->size;
    for (size_t i = 0; i < list->size; i++) {
        newList->data[i] = list->data[i];
    }
    return newList;
}

// 查找list中是否具有指定value
bool ListHas(List* list, void* value, int (*compare)(const void*, const void*)) {
    if (list == NULL) {
        fprintf(stderr, "ListHas: list is NULL\n");
        return false;
    }
    for (size_t i = 0; i < list->size; i++) {
        if (compare(list->data[i], value) == 0) {
            return true;
        }
    }
    return false;
}

// 在list中查找指定value的索引
int ListIndex(List* list, void* value, int (*compare)(const void*, const void*)) {
    if (list == NULL) {
        fprintf(stderr, "ListIndex: list is NULL\n");
        return -1;
    }
    for (size_t i = 0; i < list->size; i++) {
        if (compare(list->data[i], value) == 0) {
            return i;
        }
    }
    return -1;
}

// 删除list中的指定value
void ListRemove(List* list, void* value, int (*compare)(const void*, const void*)) {
    if (list == NULL) {
      fprintf(stderr, "ListRemove: list is NULL\n");
      return;
    }
    int index = ListIndex(list, value, compare);
    if (index == -1) {
        fprintf(stderr, "ListRemove: value is not in list");
        return;
    }
    ListDelete(list, index);
}

// value在list中出现的次数
int ListCountValue(List* list, void* value, int (*compare)(const void*, const void*)) {
    if (list == NULL) {
        fprintf(stderr, "ListCountValue: list is NULL\n");
        return -1;
    }
    int count = 0;
    for (size_t i = 0; i < list->size; i++) {
        if (compare(list->data[i], value) == 0) {
            count++;
        }
    }
    return count;
}

// 将extendList接到list后
void ListExtend(List* list, List* extendList) {
    if (list == NULL || extendList == NULL) {
        fprintf(stderr, "ListExtend: list or extendList is NULL\n");
        return;
    }
    if (list->capacity < list->size + extendList->size) {
        list->data = realloc(
            list->data, 
            (list->size + extendList->size + 10) * sizeof(void*)
        );
        if (list->data == NULL) {
            fprintf(stderr, "ListExtend: realloc failed\n");
            return;
        }
        list->capacity = list->size + extendList->size + 10;
    }
    for (size_t i = 0; i < extendList->size; i++) {
        list->data[list->size + i] = extendList->data[i];
    }
    list->size += extendList->size;
}

// 将list重复repeat次
void ListRepeat(List* list, size_t repeat) {
    if (list == NULL) {
        fprintf(stderr, "ListRepeat: list is NULL\n");
        return;
    }
    if (list->capacity < list->size * repeat) {
        list->data = realloc(
            list->data, 
            (list->size * repeat + 10) * sizeof(void*)
        );
        if (list->data == NULL) {
            fprintf(stderr, "ListRepeat: realloc failed\n");
            return;
        }
        list->capacity = list->size * repeat + 10;
    }
    for (size_t i = 0; i < list->size * repeat; i++) {
        list->data[i] = list->data[i % list->size];
    }
    list->size *= repeat;
}

// 获取list中index处的元素
void* ListGet(List* list, int index) {
    if (list == NULL) {
        fprintf(stderr, "ListGet: list is NULL\n");
        return NULL;
    }
    // 修复有符号和无符号整数比较问题
    if (index < 0) {
        // 处理负索引
        if (-index > (int)list->size) {
            fprintf(stderr, "ListGet: index out of range\n");
            return NULL;
        }
        index += list->size;
    } else {
        // 处理正索引
        if ((size_t)index >= list->size) {
            fprintf(stderr, "ListGet: index out of range\n");
            return NULL;
        }
    }
    return list->data[index];
}

// 把list中index处的元素设置为value
void ListSet(List* list, int index, void* value) {
    if (list == NULL) {
        fprintf(stderr, "ListSet: list is NULL\n");
        return;
    }
    // 修复有符号和无符号整数比较问题
    if (index < 0) {
        // 处理负索引
        if (-index > (int)list->size) {
            fprintf(stderr, "ListSet: index out of range\n");
            return;
        }
        index += list->size;
    } else {
        // 处理正索引
        if ((size_t)index >= list->size) {
            fprintf(stderr, "ListSet: index out of range\n");
            return;
        }
    }
    list->data[index] = value;
}

// 把otherList中的元素复制到list中从start到end
void ListSetFromOtherList(List* list, int start, int end, List* otherList) {
    if (list == NULL || otherList == NULL) {
        fprintf(stderr, "ListSetFromOtherList: list or otherList is NULL\n");
        return;
    }
    if (start >= list->size || end > list->size || start < -list->size || end < -list->size) {
        fprintf(stderr, "ListSetFromOtherList: index out of range\n");
        return;
    }
    if (start < 0) {
        start += list->size;
    }
    if (end < 0) {
        end += list->size;
    }
    for (size_t i = start; i < end; i++) {
        list->data[i] = otherList->data[i - start];
    }
}

// 获取list中从start到end，步数为step的元素
List* ListSlice(List* list, int start, int end, int step) {
    if (list == NULL) {
        fprintf(stderr, "ListSlice: list is NULL\n");
        return NULL;
    }
    
    // 修复有符号和无符号整数比较问题
    // 处理start索引
    if (start < 0) {
        if (-start > (int)list->size) {
            fprintf(stderr, "ListSlice: index out of range\n");
            return NULL;
        }
        start += list->size;
    } else {
        if ((size_t)start >= list->size) {
            fprintf(stderr, "ListSlice: index out of range\n");
            return NULL;
        }
    }
    
    // 处理end索引
    if (end < 0) {
        if (-end > (int)list->size) {
            fprintf(stderr, "ListSlice: index out of range\n");
            return NULL;
        }
        end += list->size;
    } else {
        if ((size_t)end > list->size) {
            fprintf(stderr, "ListSlice: index out of range\n");
            return NULL;
        }
    }
    
    if (step == 0) {
        fprintf(stderr, "ListSlice: step is 0\n");
        return NULL;
    }
    
    List* slice = ListNew();
    if (slice == NULL) {
        fprintf(stderr, "ListSlice: ListNew failed\n");
        return NULL;
    }
    for (size_t i = start; i < end; i += step) {
        ListAdd(slice, list->data[i]);
    }
    return slice;
}

// 获取list中最小的元素
void* ListMinValue(List* list, int (*compare)(const void*, const void*)) {
    if (list == NULL) {
        fprintf(stderr, "ListMinValue: list is NULL\n");
        return NULL;
    }
    if (list->size == 0) {
        fprintf(stderr, "ListMinValue: list is empty\n");
        return NULL;
    }
    void* min = list->data[0];
    for (size_t i = 1; i < list->size; i++) {
        if (compare(list->data[i], min) < 0) {
            min = list->data[i];
        }
    }
    return min;
}

// 获取list中最大的元素
void* ListMaxValue(List* list, int (*compare)(const void*, const void*)) {
    if (list == NULL) {
        fprintf(stderr, "ListMaxValue: list is NULL\n");
        return NULL;
    }
    if (list->size == 0) {
        fprintf(stderr, "ListMaxValue: list is empty\n");
        return NULL;
    }
    void* max = list->data[0];
    for (size_t i = 1; i < list->size; i++) {
        if (compare(list->data[i], max) > 0) {
            max = list->data[i];
        }
    }
    return max;
}

// 就地将列表逆序
void ListReverse(List* list) {
    for (int i = 0; i < list->size / 2; i++) {
        void* tmp = list->data[i];
        list->data[i] = list->data[list->size - 1 - i];
        list->data[list->size - 1 - i] = tmp;
    }
}

// 就地排序列表
void ListSort(List *list, int (*compare)(const void *, const void *)) {
    if (list == NULL) {
        fprintf(stderr, "ListSort: list is NULL\n");
        return;
    }
    if (list->size < 2) {
        return;
    }
    qsort(list->data, list->size, sizeof(void*), compare);
}

// 释放列表
void ListFree(List* list) {
    if (list == NULL) {
        fprintf(stderr, "ListFree: list is NULL\n");
        return;
    }
    free(list->data);
    free(list);
}